1. Field of the Invention
The present invention relates to a document layout processing method for generating a specific layout structure on the basis of a generic layout structure and the content of a particular document to be laid out, and to a device for carrying out such a method.
2. Description of the Related Art
In recent years, it has been proposed to perform Layout of a document (document processing) on the basis of the concept of a so-called structured document according to which one document is handled as a combination of a logical structure based on its sections and paragraphs and a layout structure which represents how the content of the document is to be actually arranged.
One example of document layout processing has recently been realized which is based on an office document architecture (hereinafter referred to as the "ODA") (ODA=ISO 8613: Information Processing-Text and Office System-Office Document Architecture (ODA) and Interchange Format (1989)) which belongs to the system of OSI (Open System Interconnection) proposed by the ISO (International Standards Organization).
According to the ODA, one document has, in addition to its layout structure, a logical structure which represents a structure obtained by logically grasping sections, paragraphs and the like. The content of a particular document is linked to logical objects positioned at the lowest level of a specific logical structure. FIG. 11 shows the relation between the specific logical structure and the document content linked thereto. In FIG. 11, the upper and lower portions with respect to the chain line indicated by an arrow A correspond to the specific logical structure and the document content, respectively.
The ODA enables automatic layout processing which automatically generates a specific layout structure permitted by a generic layout structure, according to document contents linked to the specific logical structure, and links the specific logical structure to a specific layout structure via the document content. To automatically generate the specific layout structure according to the document content linked to the specific logical structure indicates a series of manipulations, for example, a process in which if a certain document content is not completely laid out in a subordinate structure of a certain page object, a new page object is automatically generated and the overflown document content is laid out in the new page object.
FIG. 12 shows an example of the structure of a laid out document. In FIG. 12, the upper portion with respect to the chain line indicated by the arrow A corresponds to the specific logical structure, while the lower portion with respect to the chain line indicated by an arrow B corresponds to the specific layout structure. The example of FIG. 12 shows a case where although the content of Paragraph 2.1 of Section 2 is to be laid out on a first page, the content is too long to be laid out within the first page so that the content of Paragraph 2.1 of Section 2 is divided into halves and the latter half is laid out on a second page.
It is to be noted that, according to the ODA, each layout object class in the generic layout structure has an expression called a structure expression as an attribute "generator for subordinates" (hereinafter referred to as a "GFS") to represent a specific layout structure which can be generated. The structure expression is an expression representative of limitations of a structure immediately subordinate to a layout object belonging to a corresponding layout object class. The structure expression consists of a combination of specific terms and an object class identifier (hereinafter referred to as a "class ID").
The meaning of the terms will be described below.
It is assumed here that "a" and "b" indicate layout objects belonging to classes identified by the class IDs "A" and "B", respectively.
(1) The class ID is a symbol for primarily identifying each class within the generic layout structure.
(2) If a structure expression containing the class ID term is evaluated, one layout object belonging to a layout object class indicated by the class ID is generated as the evaluation result of the class ID term.
(3) If a structure expression containing the term SEQ is evaluated, the evaluation result of terms which follow the term SEQ indicates that the evaluated terms are linked in that order.
For example, the evaluation result of the structure expression (SEQ A B) is (a b).
(4) If a structure expression containing the term AGG is evaluated, the evaluation result of terms which follow the term AGG indicates that the evaluated terms are linked in arbitrary order.
For example, the evaluation result of the structure expression (AGG A B) is (a b) or (b a).
(5) If a structure expression containing the term CHO is evaluated, the evaluation result of terms which follow the term CHO indicates that any one of the evaluated terms is selected.
For example, the evaluation result of the structure expression (CHO A B) is (a) or (b).
(6) If a structure expression containing the term OPT is evaluated, the evaluation result is either an evaluated term which follows the term OPT or nothing.
For example, the evaluation result of the structure expression (OPT A) is (a) or "nothing".
(7) If a structure expression containing the term REP is evaluated, the evaluation result indicates that an evaluated term which follows the term REP is repeated once or an arbitrary number of times more than once.
For example, the evaluation result of the structure expression (REP A) is (a), (a a), (a a a), . . . , or (a a . . . a).
In addition, such a structure expression can be represented as a combination of terms selected from the aforesaid terms, for example, in the form of (SEQ(CHO A B)(OPT C)). The evaluation result of the structure expression (SEQ(CHO A B)(OPT C)) is (a), (a c), (b) or (b c). Each layout object class in the generic layout structure has any of the above-described structure expressions in its GFS.
Regarding the kind of immediately subordinate object which can be linked to a layout object belonging to a certain class, the layout object is limited by the structure expression contained in the GFS of the certain class. In other words, an object corresponding to any of the evaluation results of the structure expression can only be immediately linked to the layout object as a subordinate object. For example, if a layout object class whose class ID is "X" has the structure expression (SEQ(CHO A B)(OPT C)) in its GFS, the layout object a can be immediately linked to a layout object x which belongs to the layout object class having the class ID "X", but it is impossible to link both of the layout objects a and b to the same.
As a related art concerning document processing (hereinafter referred as "layout processing") which utilizes a generic structure and a specific structure to generate a specific layout structure on the basis of a document content and a generic layout structure, there is a method of sequentially generating the specific layout structure by sequentially trying a plurality of choices related to structure generation which are described in the generic layout structure. In such a method, a desired part of a document content is laid out by selecting one choice from the choices in a predetermined order. If the layout fails, the next choice is selected in the predetermined order to execute layout processing. At this time, to cancel the specific layout structure generated according to the immediately previous choice, generation and deletion of layout objects are performed so as to match the state of the layout to the new choice.
An example of the generation and deletion of layout objects resulting from the alteration of the choices will be explained below by using the above-described notation according to the ODA. For example, if the class A has the structure expression (CHO B C) as its GFS, this structure expression is evaluated on the basis of left-depth-first-search, so that B is rendered a first choice and C a second choice. A specific layout structure generated on the basis of the first choice B is as shown in FIG. 13(a). If the layout of a document content according to the specific layout structure fails, the second choice C is selected, and the layout object b which is immediately subordinate to the layout object a belonging to the class A is deleted and a layout object c is newly linked to the layout object a as an immediately subordinate object, thereby matching the specific layout structure to the second choice C. Thus, the specific layout structure is changed into that shown in FIG. 13(b).
If a class D has the structure expression (REP E) as its GFS, an n.sup.th choice is Es repeated by (n+1) times. (This evaluation method is hereinafter referred to as an "empty-box method".) A specific layout structure generated on the basis of a first choice is as shown in FIG. 14(a). In the specific layout structure, if a part of a document content is not completely laid out within a layout object e1 and the overflown document content is laid out in a layout object e2, a second choice is selected and a layout object e3 is newly linked to an object d belonging to the class D, thereby matching the specific layout structure to the second choice. Thus, the specific layout structure is changed into that shown in FIG. 14(b).
If a class F has the structure expression (OPT H) as its GFS, a first choice is "H" and a second choice is "no subordinate structure". A specific layout structure generated on the basis of the first choice H is as shown in FIG. 15(a). If the layout of a document content according to the specific layout structure fails, the second choice is selected, and a layout object h which is immediately subordinate to a layout object f belonging to the class F is deleted to match the specific layout structure to the second choice. Thus, the specific layout structure is changed into that shown in FIG. 15(b).
The above example has been described with reference to a subordinate structure which is one-level lower than a certain layout object. The following explanation is made in connection with another example in which: a class R has the structure expression (CHO U Y) as its GFS; a class U has the structure expression (SEQ V) as its GFS; and a class Y has the structure (SEQ Z) as its GFS. In this case, a layout object u is first selected as a structure which is one-level lower than the class R, and the resultant specific layout structure has an arrangement in which, as shown in FIG. 16(a), a layout object u belonging to the layout class u is generated at a level subordinate to a layout object r belonging to the class R.
In addition, since it is possible that there exits a structure which is one-level lower than the layout object class U, a layout object class V is selected. Accordingly, the specific layout structure is altered to have an arrangement in which, as shown in FIG. 16(b), the layout object v belonging to the layout class V is generated at a level subordinate to the layout object u.
If the above-described layout fails, there is no other choice in the layout object class U and the processing proceeds to a superior class, i.e., the class R. In the class R, the layout object class Y which is the second choice is selected. The specific layout structure has an arrangement in which, as shown in FIG. 16(c), the previously generated layout objects u and v are deleted and a layout object y belonging to the layout object class Y is generated at a level subordinate to the layout object r.
In addition, since it is possible that there exits a structure subordinate to the layout object class Y, a layout object class Z is selected. Accordingly, the specific layout structure is altered to have an arrangement in which, as shown in FIG. 16(d), a layout object z belonging to the layout class Z is generated at a level subordinate to the layout object y.
As described above, the conventional layout processing has been carried out by performing sequential selection from a plurality of choices related to structure generation in each class on the basis of left-depth-first-search.
However, the above-described conventional layout processing has the following problems.
(1) Since the choices are always sequentially tried in a predetermined order, if a certain kind of layout object is to be obtained, a choice may be selected which, if tried, cannot lead to generation of the required object. As a result, generation and deletion of unnecessary layout objects take place and the efficiency of layout processing is impaired.
(2) Since the dimension and position of a layout object may be set to inappropriate values, the possibility that layout processing which should succeed may fail is extremely high.
The above problem (1) will be concretely explained.
In document processing, a document writer often feels a desire to positively designate a structure in which to lay out a certain part of a logical content.
In general, the designation required to satisfy such a desire can be described as a logical content and, for example, in the ODA, a layout designation attribute corresponds to such a designation. As an example, a page break for each section corresponds to this kind of designation, and the page-break designation is achieved by assigning an attribute value "object type page" to a layout instruction attribute "new layout object" in a logical object which corresponds to a section in the ODA. In this case, it is apparent that no new page can be obtained even if the number of frames which constitute a structure subordinate to a page is increased. In the above-described conventional layout processing, however, since choices are evaluated one by one in order, unnecessary processing takes place. For example, in the example shown in FIGS. 16(a) to 16(d), even if a desired kind of layout object is the layout object z, the layout object z is not obtained so long as the layout objects u and v are not generated. This case is a problem, particularly in a case where a layout object which is unnecessarily generated and deleted is followed by a layout object which has previously been laid out. This is because each layout object holds attributes such as a dimension and a position relative to a certain reference point in accordance with the ODA and if addition or deletion of a layout object occurs before a certain layout object, it is necessary to recalculate the attribute value of the certain layout object. For example, it is assumed that, as shown in FIG. 17(a), a layout object fr1 and a layout object fr2 are laid out within one frame fr0. If the layout object fr1 is deleted, the position of the layout object fr2 varies as shown in FIG. 17(b). In this state, if a layout object fr3 having a large dimension is inserted before the layout object fr2, the layout object fr2 will overflow from the frame fr0, with the result that layout processing of the document content which has been laid out as the layout object fr2 may also be performed again. As described above, addition or deletion of an unnecessary layout object lowers the efficiency of layout processing to a remarkable extent.
The above problem (2) will be concretely described below.
This problem arises from the fact that an unnecessary layout object having no laid out content always exists in a specific layout structure because the adoption of the empty-box method and the first evaluation of the subordinate-element generator OPT permit the existence of a subordinate structure.
Consideration will be given to what happens to a generic layout structure in which, for example, a class X has the structure expression (REP P) as its GFS, a class P has the structure expression (SEQ K) as its GFS, and a class K has the structure expression (REP L)(OPT M) as its GFS. This example shows a general structure which can apply to a case where a new frame is generated for each section and if there is a footnote, a frame is generated for it. Specifically, the class X is a layout root, the class P is a page class, the class K is a frame class corresponding to a document layout, the class L is a frame class for a section, and the class M is a frame class for a footnote. It is assumed here that each of the classes K and L has a variable dimension and a variable position and that each of their dimensions has a certain fixed minimum value.
The first choice described above has the content shown in FIGS. 18(a) and 18(b). FIG. 18(a) shows a specific layout structure, and FIG. 18(b) shows a visualized example of the specific layout structure. In FIG. 18(b), the dimension of each layout object l1 and l2 which is taken in the direction indicated by an arrow A has a minimum value. It is assumed here that the logical content to be laid out is represented as a tree structure as shown in FIG. 19 and that, in each section, the class L is assigned to the layout instruction attribute "new layout object" as a value and attributes "layout category" and "permitted categories" are exclusively defined so that only the footnote can be laid out in the class M. In this case, Section 1 is laid out in the layout object l1 and the footnote is then laid out in a layout object ml. If the number of sentences for the footnote is greater than the number of sentences which can be accommodated in the layout object m1, a new choice is selected and the specific layout structure shown in FIG. 18(a) is altered to have the arrangement shown in FIG. 20(a). As a result, the overflown footnote sentences are laid out in a layout object m2. Section 2 is laid out in the layout object l2, and if the sentences of Section 2 are completely accommodated in the layout object l2, the layout is completed. In the resultant layout, nothing is laid out in a layout object l3 or a layout object l4. Since at least the layout object l3 must exist as long as a layout object p2 exists, it is determined that the layout has failed as a whole.
However, if a value obtained by adding the dimensions of the respective layout objects ml and m2 taken in the direction indicated by the arrow A of FIG. 18(b) is less than the minimum value of the dimension of the layout object l2 taken in the same direction, the layout will naturally succeed. This is because if the layout object l2 does not exist as the first choice, the layout object l1 has room to extend in the direction indicated by the arrow A of FIG. 18(b). FIGS. 21(a) and 21(b) show a specific layout structure obtained when the layout of the footnote is completed.
When Section 2 is to be laid out, not the layout object l2 but the layout object l3 is generated due to dimensional limitations and Section 2 is laid out in the layout object l3. Finally, the specific layout structure shown in FIGS. 22(a) and 22(b) is obtained and the layout succeeds. As described above, it has conventionally possible that layout processing does not accurately work because an unnecessary layout object is added to a specific layout structure.